package Stack;

import java.util.LinkedList;
import java.util.Queue;

/**
 *  题目 ：使用队列实现栈
 *  题目详述 ：
 *  请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 * 实现 MyStack 类：
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 *
 */
public class TwoQueueToStack {
    /**
     *  核心思路 ：（栈是后进先出 + 先进后出；同时队列是后进后出 + 先进先出）
     *  为实现入栈和出栈操作，使用两个队列
     *  ===> (1)queue1用来存储栈中元素 （2）queue2用来入栈操作的辅助队列（即，将入队列的元素置于队列头部[默认插入队列时，是插入队列尾部]）
     *
     *  注意 ：queue1专门用来存储栈中元素；queue2是辅助队列；
     *        即，栈中的操作 《===》 queue队列的操作
     */
    Queue<Integer> queue1;  // 用于存储栈中元素
    Queue<Integer> queue2; // 辅助队列，实现入栈时，将原本要插入队列尾部的元素，转变为插入队列头部
    public TwoQueueToStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        // 由于queue1是用于存储栈中元素的，所以需要将辅助队列queue2与queue1进行交换
        // 注意 ：原本的queue1，经过while循环后，必然为空，即交换之后，辅助队列为空
        Queue<Integer> temp = queue1; // 此时，queue1已经成为空队列（即，queue1队列中不存在任何的元素）
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        // 由于队列queue1专门用来存储栈中元素，直接将其出队列 《===》 出栈操作
        // 即，在push操作（入栈操作）后，队列的头部元素必然为栈顶元素
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {

        return queue1.isEmpty();
    }
}
